package lq1174;

import java.util.Scanner;
/*
lq1174，0/1背包，AC
输入样例1：
5 20
1 6
2 5
3 8
5 15
3 3 

输入样例2：
5 10
2 6
5 3
4 5
2 4
3 6

 */
//表示dp数组中的一个位置
//i，j为下标
class Pos{
	public int i;
	public int j;
	public Pos(int i, int j) {
		this.i = i;
		this.j = j;
	}
	@Override
	public String toString() {
		return "[" + i + "," + j + "]";
	}
	
}
public class Main {

	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int N=sc.nextInt();
		//背包容量
		int W=sc.nextInt();
		//dp数组
		int[][] c = new int[N+1][W+1];
		//w、v下标从1开始
		int[] w = new int[N+1];
		int[] v = new int[N+1];
		for(int i=1;i<=N;i++) {
			w[i] = sc.nextInt();
			v[i] = sc.nextInt();
		}
		
		//0/1背包模板代码部分
		for(int i=1;i<=N;i++) {//物品数量外层循环
			for(int j=1;j<=W;j++) {//背包容量内层循环
				if(w[i]>j) {
					//当前物品大于背包容量，不能放入
					//当前的最大价值和物品为i-1时一样
					c[i][j] = c[i-1][j];
				}else {
					//当前物品可以放入
					//比较放和不放那种价值更大
					c[i][j] = Math.max(c[i-1][j], c[i-1][j-w[i]] + v[i]);
				}
			}
		}
		
		//输出最大价值
		System.out.println(c[N][W]);
		
		//逆向构造最优解具体方案
		//方法一，详见学习资料
		/*
		StringBuilder sb = new StringBuilder();
		int j=W;
		for(int i=N;i>0;i--) {
			if(c[i][j]>c[i-1][j]) {
				sb.append(i+",");
				j = j - w[i];
			}
		}
		System.out.println(sb.toString());
		*/
		
		//逆向构造最优解具体方案
		//方法二，用from数组记录状态转移
		Pos[][] from = new Pos[N+1][W+1];
		//0/1背包模板代码部分
		for(int i=1;i<=N;i++) {//物品数量外层循环
			for(int j=1;j<=W;j++) {//背包容量内层循环
				if(w[i]>j) {
					//当前物品大于背包容量，不能放入
					//当前的最大价值和物品为i-1时一样
					c[i][j] = c[i-1][j];
					//记录状态转移来源
					//在dp数组（c数组）中是纵向转移来的
					from[i][j] = new Pos(i-1,j);
				}else {
					//当前物品可以放入
					//比较放和不放那种价值更大
					//c[i][j] = Math.max(c[i-1][j], c[i-1][j-w[i]] + v[i]);
					if(c[i-1][j]>c[i-1][j-w[i]] + v[i]) {
						c[i][j] = c[i-1][j];
						//记录状态转移来源
						//在dp数组（c数组）中是纵向转移来的
						from[i][j] = new Pos(i-1,j);
					}else {
						c[i][j] = c[i-1][j-w[i]] + v[i];
						//记录状态转移来源
						//在dp数组（c数组）中是斜向（从左上）转移来的
						from[i][j] = new Pos(i-1,j-w[i]);
					}
				}
			}
		}
		
		//输出dp数组（c数组）
		System.out.println("dp数组：");
		for(int i=1;i<=N;i++) {
			for(int j=1;j<=W;j++) {
				System.out.printf("%3d,", c[i][j]);
			}
			System.out.println();
		}
		
		//输出from数组
		System.out.println("from数组：");
		for(int i=1;i<=N;i++) {
			for(int j=1;j<=W;j++) {
				System.out.printf("%6s,", from[i][j]);
			}
			System.out.println();
		}
		
		StringBuffer sb = new StringBuffer();
		//从最大价值情况开始
		//逐一退到前面的状态
        int i = N, j = W;
        while (i > 0&&j > 0) {
        	//前一个状态和当前状态的j相等
        	//表示是纵向转移来的
        	//没有物品放入
            if (j == from[i][j].j) {
                //退到上一状态
            	//先获取上一状态的位置再复制给i和j
            	//如果直接依次从from数组赋值给i和j会导致j获取的值错误
            	Pos f = from[i][j];
            	i = f.i;
            	j = f.j;
            } else {
            	//前一个状态和当前状态的j不相等
            	//表示斜向（从左上）转移来的
            	//注意此处可确定背包里有个i号物品
                sb.append(i+",");
                //退到上一状态
                //先获取上一状态的位置再复制给i和j
            	//如果直接依次从from数组赋值给i和j会导致j获取的值错误
            	Pos f = from[i][j];
                i = f.i;
            	j = f.j;
            }
        }
        
        System.out.println("最大价值方案：");
        System.out.println(sb.toString());
	}

}
